import numpy as np
import pandas as pd
from collections import Counter, defaultdict
import string
import plotly.express as px
import plotly.offline as py
from plotly.subplots import make_subplots
import plotly.graph_objects as go
from typing import Dict
from scipy.stats import norm
from tqdm import tqdm
from IPython.display import clear_output
cyrillic_alphabet = set('абвгдеёжзийклмнопрстуфхцчшщъыьэюя')
ascii_alphabet = set(string.ascii_lowercase)
print(f'cyrillic_alphabet={sorted(list(cyrillic_alphabet))}')
print(f'ascii_alphabet={sorted(list(ascii_alphabet))}')
cyrillic_alphabet=['а', 'б', 'в', 'г', 'д', 'е', 'ж', 'з', 'и', 'й', 'к', 'л', 'м', 'н', 'о', 'п', 'р', 'с', 'т', 'у', 'ф', 'х', 'ц', 'ч', 'ш', 'щ', 'ъ', 'ы', 'ь', 'э', 'ю', 'я', 'ё'] ascii_alphabet=['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
def read_file(filename):
with open(filename, 'r') as fn:
return fn.read()
def clear_text(text, alphabet, add_space=True):
permitted_chars = alphabet
if add_space:
permitted_chars = set(alphabet) | {" "}
return ''.join(x for x in text.lower() if x in permitted_chars)
def count_n_grams(text, n=1):
counter = Counter()
for start in range(0, len(text) - n + 1):
counter.update([text[start : start+n]])
return counter
def read_corpus(filename, alphabet, n_gram_size=1, add_space=True):
text = read_file(filename)
text = clear_text(text, alphabet, add_space)
return count_n_grams(text, n_gram_size)
def corpus_to_df(corpus):
df = pd.DataFrame([dict(char=k, count=v) for k,v in corpus.items()])
total_num = float(sum(corpus.values()))
df['count'] /= total_num
return df.sort_values('char')
def generate_samples(filename, alphabet, min_len, max_len, number_of_samples, add_space=True):
sample = read_file(filename)
sample = [clear_text(x, alphabet, add_space) for x in sample.split('\n')]
sample = [x for x in sample if min_len <= len(x) <= max_len]
return np.random.choice(sample, number_of_samples)
def permutate(sample):
chars = list(set(sample))
original_chars = list(set(sample))
np.random.shuffle(chars)
permutation = {orig: to for orig, to in zip(original_chars, chars)}
# for orig, to in zip(original_chars, chars):
# print(f'replacing {orig} -> {to}')
return ''.join(permutation[c] for c in sample), permutation
def unpermutate(permutated_text, permutation):
inversed_index = {v:k for k,v in permutation.items()}
return ''.join(inversed_index[c] for c in permutated_text)
def freq_to_sorted_list(freq: Dict):
return sorted([(k,v) for k,v in freq.items()], key=lambda x: -x[-1])
def plot_accuracy(x, y, title, window):
fig = px.scatter(x=x, y=y, title=title,
labels={'x': 'length of sample', 'y': 'accuracy'})
sums, counts = defaultdict(float), defaultdict(int)
for xi, yi in zip(x, y):
x_key = xi // window * window
sums[x_key] += yi
counts[x_key] += 1
mean_x = sorted(sums.keys())
fig.add_scatter(x=mean_x, y=[sums[xi]/counts[xi] for xi in mean_x], name='mean line', opacity=0.7, )
return fig
def try_decode(encoded, guess):
return ''.join(guess[c] for c in encoded)
print(f"Example of cleared text:\n\t{clear_text(read_file('WarAndPeace.txt'), cyrillic_alphabet)[:400]}")
wap_corpus = read_corpus('WarAndPeace.txt', cyrillic_alphabet)
fig = px.histogram(corpus_to_df(wap_corpus), x='char', y='count',
labels={'count':'char count'},
title='Chars distribution')
py.iplot(fig)
Example of cleared text: война и мир самый известный роман льва николаевича толстого как никакое другое произведение писателя отражает глубину его мироощущения и философииэта книга из разряда вечных потому что она обо всем о жизни и смерти о любви и чести о мужестве и героизме о славе и подвиге о войне и мирепервый том знакомит с высшим обществом россии века показаны взаимоотношения между родителями и детьми в семье ро
def try_decode_1gram(sample, corpus):
sample_freq = count_n_grams(sample, n=1)
sample_freq = freq_to_sorted_list(sample_freq)
corpus_freq = freq_to_sorted_list(corpus)
inverted_index = {}
for sc, cc in zip(sample_freq, corpus_freq):
from_c, _ = sc
to_c, _ = cc
inverted_index[from_c] = to_c
# print(f'encoding {from_c} -> {to_c}')
return ''.join(inverted_index[c] for c in sample)
def char_accuracy(s1, s2):
total = 0
equal = 0
for c1, c2 in zip(s1, s2):
total += 1
equal += c1 == c2
return 100.0 * equal / total
debug_output = False
x, y = [], []
samples = generate_samples('AnnaKarenina.txt', cyrillic_alphabet,
min_len=100, max_len=1000, number_of_samples=1000)
for sample in samples:
encoded, permutation = permutate(sample)
decoded = try_decode_1gram(encoded, wap_corpus)
acc = char_accuracy(sample, decoded)
x.append(len(sample))
y.append(acc)
if debug_output:
print (f'Original sample:\n\t{sample}\nDecoded sample:\n\t{decoded}')
print(f'Accuracy: {acc:0.1f}%')
fig = plot_accuracy(x=x, y=y, title='One-gram frequency analysis', window=10)
py.iplot(fig)
bigrams = read_corpus('WarAndPeace.txt', cyrillic_alphabet, n_gram_size=2, add_space=False)
sorted_cyrrilic_abc = sorted(list(cyrillic_alphabet))
bigrams_dist = np.zeros((len(sorted_cyrrilic_abc), len(sorted_cyrrilic_abc)))
for i, a in enumerate(sorted_cyrrilic_abc):
for j, b in enumerate(sorted_cyrrilic_abc):
bigrams_dist[i][j] = bigrams.get(a + b, 0.0)
print(f'Most common bigrams: {bigrams.most_common(10)}')
fig = px.imshow(
bigrams_dist,
labels=dict(x="Second letter", y="First letter", color="Couccurance"),
x=sorted_cyrrilic_abc,
y=sorted_cyrrilic_abc,
title="Bigrams distribution"
)
py.iplot(fig)
Most common bigrams: [('то', 8663), ('ст', 6846), ('на', 6585), ('ов', 6487), ('ал', 5857), ('го', 5802), ('он', 5621), ('не', 5581), ('но', 5542), ('ко', 5494)]
most_frequent_bigrams = bigrams.most_common(100)
fig = px.histogram(
x=[i[0] for i in most_frequent_bigrams],
y=[i[1] for i in most_frequent_bigrams],
labels={'x': 'bigrams', 'y': 'count'},
title='100 most common bigrams'
)
py.iplot(fig)
Поискав в Интеренете, про биграммный поиск пишут, что он просто аналогичен обычному. Тем не менее, у меня не сложилось четкого понимания, как декодировать с помощью биграмм. Очевидно, мы считаем частоту совстречаемости пар символов. Однако, дальше возникает вопрос, что делать.
Например, вот у нас в закодированной последовательности встречается такая комбинация: $$a_{t-1} a_t a_{t+1} a_{t+2}$$ Пусть мы знаем, что среди них $a_t a_{t+1}$ являются самой частой парой, и в соответствии с корпусом, мы им назначаем пару $b_t b_{t+1}$. Дальше возникает вопрос, как действовать. Например, пара $a_{t-1} a_t$ является следующей по частоте встречаемости, но ей соответсвует (по частоте в корпусе), пара $c_{t-1} c_{t}$, при чем $c_t \neq b_t$
Как поступать в таком случае?
В реализованном ниже примере используется следующий подход: мы выбираем наиболее вероятную пару из допустимых. То есть, в данном случае, мы наложим ограничение на выбор $c_{t} \equiv b_{t}$. Это позволяет однозначным образом декодировать. Недостатком является накапливание ошибки: если мы плохо декодировали самую вероятную пару, то дальше алгоритм уже не выправится.
class BiGramDecoder:
def __init__(self, alphabet, corpus_text):
self.alphabet = set(alphabet)
self.corpus_freq = count_n_grams(corpus_text, n=2)
self.corpus_freq_list = freq_to_sorted_list(self.corpus_freq)
self.already_processed = {}
def _decode(self, a, b):
if a in self.already_processed and b in self.already_processed:
return self.already_processed[a], self.already_processed[b]
elif a in self.already_processed:
best_p = -1.0
best_c = None
decoded_a = self.already_processed[a]
for c in self.alphabet - set(self.already_processed.values()):
if self.corpus_freq[decoded_a + c] > best_p:
best_p = self.corpus_freq[decoded_a + c]
best_c = c
self.already_processed[b] = c
return decoded_a, c
elif b in self.already_processed:
best_p = -1.0
best_c = None
decoded_b = self.already_processed[b]
for c in self.alphabet - set(self.already_processed.values()):
if self.corpus_freq[c + decoded_b] > best_p:
best_p = self.corpus_freq[c + decoded_b]
best_c = c
self.already_processed[a] = c
return c, decoded_b
else:
used = set(self.already_processed.values())
for seq, _ in self.corpus_freq_list:
c, d = seq
if c not in used and d not in used:
self.already_processed[a] = c
self.already_processed[b] = d
return c, d
def __call__(self, sample):
assert len(self.already_processed) == 0
sample_freq = freq_to_sorted_list(count_n_grams(sample, n=2))
letters_in_sample = len(set(sample))
for seq, cnt in sample_freq:
a, b = self._decode(seq[0], seq[1])
# print(f'{seq}[{cnt}] -> {a}{b}')
if len(self.already_processed) == letters_in_sample:
break
# print(self.already_processed)
# print(sample)
return ''.join(self.already_processed[c] for c in sample)
def reset(self):
self.already_processed = {}
debug_output = False
x, y = [], []
corpus_text = clear_text(read_file('WarAndPeace.txt'), cyrillic_alphabet, add_space=False)
decoder = BiGramDecoder(cyrillic_alphabet, corpus_text)
samples = generate_samples('AnnaKarenina.txt', cyrillic_alphabet, add_space=False,
min_len=200, max_len=2000, number_of_samples=1000)
for sample in samples:
encoded, permutation = permutate(sample)
decoder.reset()
decoded = decoder(encoded)
acc = char_accuracy(sample, decoded)
x.append(len(sample))
y.append(acc)
if debug_output:
print (f'Original sample:\n\t{sample}\nDecoded sample:\n\t{decoded}')
print(f'Accuracy: {acc:0.1f}%')
fig = plot_accuracy(x=x, y=y, title='Bi-gram frequency analysis', window=20)
py.iplot(fig)
Как видно, результат получился очень неустойчивым, и в среднем хуже, чем для униграмм.
Будем исходить из предположение, что частота встречаемости биграмм распределена нормально со средним, посчитанным по корпусу и некоторой дисперсией (которую как раз подберем по MCMC-алгоритму, смотря на количество принятых/отброшенных сэмплов). Тогда мы сможем определить вероятность встретить биграмму с такой частотой в примере по функцию нормального распределения: $$p(ab) = f(freq_{ab}, N(mu_{ab}, std))$$ где $freq_{ab}$ - частота пары $ab$ в примере, $mu_{ab}$ - частота пары $ab$ на корпусе
И в итоге можно получить вероятность данной перестановки путем произведенеия вероятностей для каждой из биграмм
def get_log_proba(prediction, sample_pairs, corpus_pairs, std):
MIN_RATIO = 1e-6
res = 0
# print(f'get_log_proba->{sample_pairs}')
for s_pair, x in sample_pairs.items():
c_pair = prediction[s_pair[0]] + prediction[s_pair[1]]
mu = corpus_pairs.get(c_pair, MIN_RATIO)
# print(s_pair, x, mu, norm.logpdf(x, mu, std))
res += norm.logpdf(x, mu, std)
return res # np.exp(res)
Сделаем MCMC алгоритм. В качестве отдельного шага будем менять буквы в перестановке, и смотреть, как это отразится на итоговой вероятности перестановки. Выбор букв для замены будем делать равновероятным (то есть распределение для сэмплирование $q(x^{t+1}|x^t)$ - получается симметричным).
Тогда алгоритм следующий:
class MCMC:
def __init__(self, corpus_text, std):
corpus = count_n_grams(corpus_text, n=2)
total = sum(corpus.values())
self.corpus_chars = count_n_grams(corpus_text, n=1)
self.corpus_pairs = {key: value/total for key, value in corpus.items()}
self.std = std
def make_n_steps(self, sample_text, n, initial_x=None):
sample_pairs = count_n_grams(sample_text, n=2)
sample_total = sum(sample_pairs.values())
sample_pairs = {key: value/sample_total for key, value in sample_pairs.items()}
# print(f"initial_x: {initial_x}")
chars = list(set(sample_text))
if initial_x is not None:
x = initial_x.copy()
p_cur = get_log_proba(initial_x, sample_pairs, self.corpus_pairs, self.std)
p_next = get_log_proba(x, sample_pairs, self.corpus_pairs, self.std)
# print(f'Set initial state, starts from , {p_cur} <-> {p_next}')
else:
temp = [p[0] for p in self.corpus_chars.most_common(len(chars))]
np.random.shuffle(temp)
x = {c:to_c for c, to_c in zip(chars, temp)}
hist = []
accepted_count = 0
accepted_negative = 0
below = 0
for i in tqdm(range(n)):
a, b = np.random.choice(chars, 2, False)
x_next = x.copy()
x_next[a], x_next[b] = x_next[b], x_next[a]
# print(f'step_{i}, {a, b, x[b], x[a]}, {get_proba(x, sample_pairs, self.corpus_pairs, self.std)}')
p_cur = get_log_proba(x, sample_pairs, self.corpus_pairs, self.std)
p_next = get_log_proba(x_next, sample_pairs, self.corpus_pairs, self.std)
hist.append(p_cur)
a = p_next - p_cur
below += a < 0
# print(f'a={a}, p_next={p_next}, p_cur={p_cur}')
if a >= 0:
x = x_next
accepted_count += 1
else:
if np.random.random() < np.exp(a):
x = x_next
accepted_count += 1
accepted_negative += 1
print(f'Total steps: {n}, accepted={accepted_count} ({100.0*accepted_count/n}%),',
f'below_zero={below}, accepted_negative={accepted_negative}')
hist.append(get_log_proba(x, sample_pairs, self.corpus_pairs, self.std))
return x, hist, 100.0*accepted_count/n
Подберем значение стандартного отклонения в нормальном распределении так, чтоб число принятых было на уровне 0.5
corpus_text = clear_text(read_file('WarAndPeace.txt'), cyrillic_alphabet)
samples = generate_samples('AnnaKarenina.txt', cyrillic_alphabet,
min_len=100, max_len=1000, number_of_samples=5)
std_candidates = np.linspace(0.0001, 0.01, 40)
accepted_hist = []
for std in std_candidates:
print(f'std={std}')
sum_accepted = 0
mcmc = MCMC(corpus_text, std)
for sample in samples:
x, hist, accepted_ratio = mcmc.make_n_steps(sample, 500)
sum_accepted += accepted_ratio
clear_output()
accepted_hist.append(sum_accepted / len(samples))
fig = px.line(x=std_candidates, y=accepted_hist, title='Selecting std for gaus-dist (in MCMC)',
labels={'x': 'std', 'y': 'mean accepted ratio'})
py.iplot(fig)
Для более точного предсказания предлагается также сделать двухэтапную схему: сначала выходим на плато (по $p(X_{permutation})$), а затем понижаем STD, чтоб брать отбирать только наиболее вероятные перестановки. Ниже показан пример, как зависит точность предсказания от понижение std (каждую эпоху снижаем в два раза)
corpus_text = clear_text(read_file('WarAndPeace.txt'), cyrillic_alphabet)
sample_text = generate_samples('AnnaKarenina.txt', cyrillic_alphabet,
min_len=300, max_len=1000, number_of_samples=1)[0]
std = 0.1
decrease_count = 20
mcmc = MCMC(corpus_text, std=std)
accuracy_hist = []
accepted_hist = []
std_hist = []
hist = []
x0 = None
for i in range(decrease_count):
clear_output()
mcmc.std = std
std_hist.append(std)
x0, hist_cur, accepted_ratio = mcmc.make_n_steps(sample_text, 5000, x0)
hist += hist_cur
decoded = ''.join(x0[c] for c in sample_text)
acc = char_accuracy(sample_text, decoded)
accuracy_hist.append(acc)
accepted_hist.append(accepted_ratio)
print(f"Done {i+1} for std={std}")
std = std / 2
fig = make_subplots(
rows=3, cols=2,
specs=[[{"colspan": 2}, {}],
[{"colspan": 2}, {}],
[{}, {}]],
subplot_titles=("Score proportional the probability of permutation based on bigrams distribution", None,
"Accuracy of decoding", None,
"STD decline through epoch",
"Percent of accepted samples"),
)
fig.add_trace(go.Scatter(x=np.arange(len(hist)), y=hist, ),
row=1, col=1)
fig.add_trace(go.Scatter(x=np.arange(len(accuracy_hist)), y=accuracy_hist),
row=2, col=1)
fig.add_trace(go.Scatter(x=np.arange(len(std_hist)), y=std_hist),
row=3, col=1)
fig.add_trace(go.Scatter(x=np.arange(len(accepted_hist)), y=accepted_hist),
row=3, col=2)
fig.update_layout(showlegend=False, title_text="Decreasing std through epochs", height=1200)
py.iplot(fig)
100%|██████████| 5000/5000 [04:00<00:00, 20.78it/s]
Total steps: 5000, accepted=0 (0.0%), below_zero=5000, accepted_negative=0 Done 20 for std=1.9073486328125e-07
STD=0.008
corpus_text = clear_text(read_file('WarAndPeace.txt'), cyrillic_alphabet)
samples = generate_samples('AnnaKarenina.txt', cyrillic_alphabet,
min_len=100, max_len=1000, number_of_samples=10)
mcmc = MCMC(corpus_text, std=STD)
hist_by_sample = []
steps_number = 3000
for i, sample in enumerate(samples):
_, hist, _ = mcmc.make_n_steps(sample, steps_number)
hist_by_sample.append(hist)
clear_output()
print(f"Done {i+1}/{len(samples)}")
Done 10/10
x = np.arange(len(hist_by_sample[0]))
fig = px.line(x=x, y=hist_by_sample[0],
labels={"x": "steps", "y": "function that is proportinal to probability"},
title="Number of steps for convergence")
for hist in hist_by_sample[1:]:
fig.add_scatter(x=x, y=hist)
py.iplot(fig)
В целом видно, что 1000 шагов хватает для того, чтоб MCMC вышел на плато. Будем выполнять эти шаги перед началом семплирования
INITIAL_STEPS = 1000
corpus_text = clear_text(read_file('WarAndPeace.txt'), cyrillic_alphabet)
samples = generate_samples('AnnaKarenina.txt', cyrillic_alphabet,
min_len=100, max_len=1000, number_of_samples=40)
samples = sorted(samples, key=len)
mcmc = MCMC(corpus_text, std=STD)
samples_per_text = 10
samples_len = []
samples_acc = []
all_log = []
for sample in samples:
encoded, permutation = permutate(sample)
mcmc.std = STD
x, _, _ = mcmc.make_n_steps(encoded, INITIAL_STEPS)
mcmc.std /= 2
sample_accuracy = 0
for _ in range(samples_per_text):
res = mcmc.make_n_steps(encoded, np.random.randint(20, 100), initial_x=x)
x, _, _ = res
decoded = ''.join(x[c] for c in encoded)
acc = char_accuracy(sample, decoded)
all_log.append({
'sample': sample,
'encoded': encoded,
'permutation': permutation,
'res': res,
'acc': acc
})
sample_accuracy += acc
samples_len.append(len(sample))
samples_acc.append(sample_accuracy / samples_per_text)
clear_output()
Пример успешного декодирования методом MCMC:
# all_log1 = all_log
best_decoding = np.argmax([x['acc'] for x in all_log])
best = all_log[best_decoding]
print(f'Original sample:\n\t{best["sample"]}')
print(f'Ecoded sample:\n\t{best["encoded"]}')
guessed_permutation = best['res'][0]
decoded = ''.join(guessed_permutation[c] for c in best['encoded'])
print(f'Decoded sample:\n\t{decoded}')
print(f'Accuracy: {best["acc"]}%')
Original sample: кити не рассердись но ты подумай дело это так важно что мне больно думать что ты смешиваешь чувство слабости нежелания остаться одной ну тебе скучно будет одной ну поезжай в москву Ecoded sample: етш шеякеучжжкуишжлеясе вепсирычдеикьсеэ се чтеачйясез сеыякемсьлясеирыч лез се вежыкншачкнлезраж асежьчмсж шеякйкьчяшбесж ч лжбесиясдеяре кмкежтрзясемрик есиясдеярепскойчдеаеысжтар Decoded sample: лити не массемдись но ты годукая деро бто тал вазно что кне порьно дукать что ты скеживаежь чувство срапости незераний остатьсй одноя ну тепе случно пудет одноя ну гоешзая в кослву Accuracy: 81.21546961325967%
fig = px.line(x=samples_len, y=samples_acc, title='Accuracy', labels={'x': 'sample length', 'y': 'accuracy'})
py.iplot(fig)
encoded = "←⇠⇒↟↹↷⇊↹↷↟↤↟↨←↹↝⇛⇯↳⇴⇒⇈↝⇊↾↹↟⇒↟↹⇷⇛⇞↨↟↹↝⇛⇯↳⇴⇒⇈↝⇊↾↹↨←⇌⇠↨↹⇙↹⇸↨⇛↙⇛↹⇠⇛⇛↲⇆←↝↟↞↹⇌⇛↨⇛⇯⇊↾↹⇒←↙⇌⇛↹⇷⇯⇛⇞↟↨⇴↨⇈↹⇠⇌⇛⇯←←↹↷⇠←↙⇛↹↷⇊↹↷⇠←↹⇠↤←⇒⇴⇒↟↹⇷⇯⇴↷↟⇒⇈↝⇛↹↟↹⇷⇛⇒⇙⇞↟↨←↹↳⇴⇌⇠↟↳⇴⇒⇈↝⇊↾↹↲⇴⇒⇒↹⇰⇴↹⇷⇛⇠⇒←↤↝←←↹⇞←↨↷←⇯↨⇛←↹⇰⇴↤⇴↝↟←↹⇌⇙⇯⇠⇴↹↘⇛↨↞↹⇌⇛↝←⇞↝⇛↹↞↹↝↟⇞←↙⇛↹↝←↹⇛↲←⇆⇴⇏"
print (encoded)
←⇠⇒↟↹↷⇊↹↷↟↤↟↨←↹↝⇛⇯↳⇴⇒⇈↝⇊↾↹↟⇒↟↹⇷⇛⇞↨↟↹↝⇛⇯↳⇴⇒⇈↝⇊↾↹↨←⇌⇠↨↹⇙↹⇸↨⇛↙⇛↹⇠⇛⇛↲⇆←↝↟↞↹⇌⇛↨⇛⇯⇊↾↹⇒←↙⇌⇛↹⇷⇯⇛⇞↟↨⇴↨⇈↹⇠⇌⇛⇯←←↹↷⇠←↙⇛↹↷⇊↹↷⇠←↹⇠↤←⇒⇴⇒↟↹⇷⇯⇴↷↟⇒⇈↝⇛↹↟↹⇷⇛⇒⇙⇞↟↨←↹↳⇴⇌⇠↟↳⇴⇒⇈↝⇊↾↹↲⇴⇒⇒↹⇰⇴↹⇷⇛⇠⇒←↤↝←←↹⇞←↨↷←⇯↨⇛←↹⇰⇴↤⇴↝↟←↹⇌⇙⇯⇠⇴↹↘⇛↨↞↹⇌⇛↝←⇞↝⇛↹↞↹↝↟⇞←↙⇛↹↝←↹⇛↲←⇆⇴⇏
encoded_freq = count_n_grams(encoded, 1)
most_frequent_unigrams = encoded_freq.most_common(100)
fig = px.histogram(
x=[i[0] for i in most_frequent_unigrams],
y=[i[1] for i in most_frequent_unigrams],
labels={'x': 'char', 'y': 'count'},
title='Frequence of chars'
)
py.iplot(fig)
encoded_bifreq = count_n_grams(encoded, 2)
most_frequent_bigrams = encoded_bifreq.most_common(100)
fig = px.histogram(
x=[i[0] for i in most_frequent_bigrams],
y=[i[1] for i in most_frequent_bigrams],
labels={'x': 'bigram', 'y': 'count'},
title='Frequence of bigrams (100 most frequent)'
)
py.iplot(fig)
corpus_text = clear_text(read_file('WarAndPeace.txt'), cyrillic_alphabet)
mcmc = MCMC(corpus_text, std=STD)
guess, hist, accepted_ratio = mcmc.make_n_steps(encoded, INITIAL_STEPS)
fig = px.line(x=np.arange(len(hist)), y=hist,
labels={"x": "steps", "y": "function that is proportinal to probability"},
title="Convergence of MCMC")
py.iplot(fig)
100%|██████████| 1000/1000 [00:30<00:00, 32.62it/s]
Total steps: 1000, accepted=465 (46.5%), below_zero=769, accepted_negative=234
def replace_chars(to_replace, guess):
inverted_index = {v: k for k,v in guess.items()}
for from_char, to_char in to_replace.items():
if to_char in inverted_index:
inverted_index[from_char], inverted_index[to_char] = inverted_index[to_char], inverted_index[from_char]
else:
inverted_index[to_char] = inverted_index[from_char]
del inverted_index[from_char]
return {v: k for k,v in inverted_index.items()}
best = -1000
best_x = None
# x = guess
improved = 0
mcmc.std = STD
hypotheses = []
for _ in range(100):
clear_output(True)
x, h, _ = mcmc.make_n_steps(encoded, 20, x)
hypotheses.append(x)
if h[-1] > best:
best = h[-1]
best_x = x
improved += 1
clear_output(True)
print(f'Number of improve: {improved}')
Number of improve: 6
Первые два слова очень похожи на "если вы". Попробуем заменить их. и далее раскрутить
guess = hypotheses[5]
print(f"Originally guess: {guess}")
print(f"Originally: {try_decode(encoded, guess)}")
guess = replace_chars({'и': 'с', 'р': 'л', 'а': 'и', 'ю': 'д'}, guess)
guess = replace_chars({'ю': 'т', 'м': 'п', 'к': 'ч'}, guess)
guess = replace_chars({'н': 'к', 'а': 'р', 'я': 'й'}, guess)
guess = replace_chars({'м': 'н', 'ь': 'а', 'у': 'ь', 'я': 'б', 'ю': 'з', 'ш': 'х', }, guess)
guess = replace_chars({'ж': 'я'}, guess)
guess = replace_chars({'ж': 'э', 'у': 'щ', 'ю': 'у'}, guess)
print(f"Guess: {guess}")
# print(f"Encoded: {encoded}")
print(f"Decoded: {try_decode(encoded, guess)}")
Originally guess: {'⇙': 'з', '↝': 'п', '⇈': 'у', '⇠': 'и', '←': 'е', '↞': 'ж', '⇴': 'ь', '⇰': 'т', '⇛': 'о', '↨': 'д', '↟': 'а', '↹': ' ', '↷': 'в', '⇷': 'м', '⇆': 'л', '⇒': 'р', '↘': 'ш', '⇞': 'к', '↾': 'я', '↤': 'ю', '⇊': 'ы', '⇸': 'б', '↲': 'й', '↳': 'ч', '⇌': 'н', '↙': 'г', '⇏': 'х', '⇯': 'с'}
Originally: еира вы ваюаде посчьрупыя ара мокда посчьрупыя денид з бдого иоойлепаж нодосыя регно мсокадьду иносее виего вы вие июерьра мсьварупо а морзкаде чьниачьрупыя йьрр ть моиреюпее кедвесдое тьюьпае нзсиь шодж нопекпо ж пакего пе ойельх
Guess: {'⇰': 'з', '⇷': 'п', '↟': 'и', '←': 'е', '⇈': 'ь', '↨': 'т', '⇛': 'о', '↤': 'д', '⇴': 'а', '↹': ' ', '↷': 'в', '↳': 'м', '⇒': 'л', '⇯': 'р', '⇏': 'ш', '⇌': 'к', '↞': 'я', '⇊': 'ы', '↲': 'б', '↾': 'й', '⇞': 'ч', '↝': 'н', '↙': 'г', '↘': 'х', '⇠': 'с', '⇸': 'э', '⇆': 'щ', '⇙': 'у'}
Decoded: если вы видите нормальный или почти нормальный текст у этого сообщения который легко прочитать скорее всего вы все сделали правильно и получите максимальный балл за последнее четвертое задание курса хотя конечно я ничего не обещаш
Еще некорые получавшиеся гипотезы:
best_x = replace_chars({'к': 'с'}, best_x)
print(f"Decoded: {try_decode(encoded, best_x)}")
Decoded: если кя кишите новбыльняа или подти новбыльняа тегст ю хторо соомжениу готовяа лерго пводитыть сговее ксеро кя ксе сшелыли пвыкильно и полюдите быгсибыльняа мылл чы послешнее деткевтое чышыние гювсы зоту гонедно у нидеро не омежый
best_x = replace_chars({'я': 'ы'}, best_x)
print(f"Guess: {best_x}")
print(f"Encoded: {encoded}")
print(f"Decoded: {try_decode(encoded, best_x)}")
Guess: {'⇙': 'ю', '↝': 'н', '⇈': 'ь', '⇷': 'к', '←': 'е', '↞': 'у', '⇊': 'ы', '⇰': 'ч', '⇛': 'о', '↷': 'т', '↟': 'и', '↹': ' ', '⇠': 'с', '↨': 'п', '⇆': 'ж', '⇒': 'л', '↘': 'з', '⇞': 'д', '↾': 'а', '↤': 'ш', '⇴': 'я', '⇸': 'х', '↲': 'м', '↳': 'б', '⇌': 'г', '↙': 'р', '⇏': 'й', '⇯': 'в'}
Encoded: ←⇠⇒↟↹↷⇊↹↷↟↤↟↨←↹↝⇛⇯↳⇴⇒⇈↝⇊↾↹↟⇒↟↹⇷⇛⇞↨↟↹↝⇛⇯↳⇴⇒⇈↝⇊↾↹↨←⇌⇠↨↹⇙↹⇸↨⇛↙⇛↹⇠⇛⇛↲⇆←↝↟↞↹⇌⇛↨⇛⇯⇊↾↹⇒←↙⇌⇛↹⇷⇯⇛⇞↟↨⇴↨⇈↹⇠⇌⇛⇯←←↹↷⇠←↙⇛↹↷⇊↹↷⇠←↹⇠↤←⇒⇴⇒↟↹⇷⇯⇴↷↟⇒⇈↝⇛↹↟↹⇷⇛⇒⇙⇞↟↨←↹↳⇴⇌⇠↟↳⇴⇒⇈↝⇊↾↹↲⇴⇒⇒↹⇰⇴↹⇷⇛⇠⇒←↤↝←←↹⇞←↨↷←⇯↨⇛←↹⇰⇴↤⇴↝↟←↹⇌⇙⇯⇠⇴↹↘⇛↨↞↹⇌⇛↝←⇞↝⇛↹↞↹↝↟⇞←↙⇛↹↝←↹⇛↲←⇆⇴⇏
Decoded: если ты тишипе новбяльныа или кодпи новбяльныа пегсп ю хпоро соомжениу гоповыа лерго кводипяпь сговее тсеро ты тсе сшеляли квятильно и колюдипе бягсибяльныа мялл чя кослешнее дептевпое чяшяние гювся зопу гонедно у нидеро не омежяй